Any digital data traversing a network must be routed. While an end user in California checking a website hosted in the United Kingdom is more concerned about receiving information from that website than how the information travels, the stream of packets representing the user request and the web server response are routed through a number of networks; it is possible that not all the packets involved take the same route.
Routers are specialized computers which forward messages to their respective destinations. One of the tasks of the router is to determine the most effective and/or efficient route for a packet to take. The router switches packets of information between multiple ports connected to other routers and intervening networks.
The intervening networks are constructed as independently administrated domains known as Autonomous Systems (AS). Autonomous Systems are comprised of a set of routers and interconnecting paths, but are managed and appear to the outside world as monolithic entities. Packets are routed based on a routing information database. The routing information database within an AS is a result of intra-domain routing protocol processing where the routing information exchanged between ASes is done by intra-domain routing protocols. For inter domain, routing information is typically exchanged using inter-domain routing protocols. Dissemination of inter-domain routing information is a subject of routing policies. These policies have both technical and business aspects.
Technical aspects of routing policies have to do with the most efficient routing of packets. For example, a gigabit link is usually preferred over a T-1 line as it is faster. Routes with fewer hops are usually preferred.
Business aspects of routing policies have to do with cost and business decisions. For example, a business may contract with more than one service provider, routing most of its traffic through one provider and using the second as backup. An AS may base routing on contractual obligations, for example, a contractual obligation to provide a customer with a specified quality of service (QoS) may affect routing policy. An AS uses routing policy to restrict traffic carried on certain high-capacity links to those customers willing to pay a premium for the service. Different ISPs (Internet Service Providers) will apply different routing policies depending with whom they peer.
An ISP or AS should apply its routing policies across all elements of its network, insuring that policies are applied consistently. These routing policies determine, for example, which prefixes are accepted by an AS, from whom, and which prefixes are advertised by the AS, and to whom. Routing policy may also state how prefixes are aggregated, as well as the use of MEDs (Multi-Exit Discriminator) and communities, and the use of damping parameters to control issues such as flapping.
Within an AS the routing information is distributed via intra-domain routing protocols such as the Routing Information Protocol (RIP), Open Shortest Path First Protocol (OSPF), or Intermediate System to Intermediate System (ISIS). Inter-domain routing information is usually distributed via the industry standard Border Gateway Protocol (BGP), or the like. Internally within an AS, BGP exchanges routing information between border routers using iBGP and between ASes using eBGP. Only border routers are involved in BGP routing information exchange. Border routers are those operating on the edges of an AS.
While an AS may appear as a monolithic entity, it is comprised of a myriad of routers and links between those routers. Each router and each link present possible sources of trouble. Trouble may be in the nature of injudicious backhoe operators, faulty connectors, power outages, operator errors, misconfigured routers, or miscommunication between routers. Some of the intra-domain routing changes effect inter-domain routing information.
In a system such as an AS which could be geographically distributed, and contains a myriad of variables such as the operating states of border routers and the links between them, how does the AS operator verify that the routing policies they have put in place have been deployed through the AS and are actually operating? How may an ISP customer verify that his/her ISP is implementing the routing policies for which they have contracted?
Existing solutions monitor BGP and similar exchanges in the target network, gathering routing information at specific locations under the assumption that all border routers of a particular AS behave in the same manner. These solutions suffer from a number of difficulties. First, they can only model the network to the extent of the information received. Even collecting all BGP sessions from all border routers will not guarantee that the disseminated routing information is the same as that reported by the BGP sessions. Extra BGP sessions are required to perform such monitoring, increasing the overhead on monitored routers. Second, prefixes which are blocked will not be visible unless there are also established BGP sessions with other ASes which advertise those prefixes. This means that in order to discover if routes are blocked by a specific border router, a BGP session must be established with a router that advertises the questionable prefixes and with a router which accepts those prefixes. Third, router configuration in the form of BGP sessions or similar information is at least one level removed from the policies being implemented; BGP session data represents the effect or implementation of policy, not the policy itself.
Additionally, data acquired from monitoring BGP sessions describes the network as it is supposed to be, rather than as the network actually is, complete with router misconfigurations, operator errors, faulty equipment, and the myriad of troubles which differentiates the real world from the purity of abstract models.
What is needed is a non-intrusive way to discover routing policies of Autonomous System.